package Offer.offer2020;

/**
 * 旋转数组的最小数字
 * 先考虑正常情况（4,5,6,7,1,2,3），start比end大，
 * mid如果比start大，说明最小值在mid和end之间
 * mid如果比start小，说明最小值在start和mid之间
 * <p>
 * 特殊情况一(1,2,3,4,5),未旋转
 * 第0个元素即是最小数
 * <p>
 * 特殊情况二(2,0,1,1,2),start=end & mid < start
 * 最小值在start和mid之间
 * <p>
 * 特殊情况三(2,3,4,1,2),start=end & mid > start
 * 最小值在mid和end之间
 * <p>
 * 特殊情况四(1,0,1,1,1),start=end=mid，无法区分最小值位置
 * 直接遍历
 */
public class Test08 {

    public int findMin(int[] array) {
        if (array == null || array.length == 0) {
            throw new RuntimeException("数组为空！");
        }

        int start = 0;
        int end = array.length - 1;

        if (array[start] < array[end]) {
            return array[start];
        }
        int mid = (start + end) >> 1;
        if (array[start] == array[end] && array[start] == array[mid]) {
            //直接遍历
            return findMidAsOrder(array);
        }
        while (start < end) {
            mid = (start + end) >> 1;
            if (array[mid] >= array[start]) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return array[start];
    }

    private int findMidAsOrder(int [] array) {
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
        }
        return min;
    }
}
